class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}


public class LeetCode {
    //24. 两两交换链表中的节点
    //1.递归
    public ListNode swapPairs1(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode tmp = swapPairs1(head.next.next);
        ListNode newhead = head.next;
        head.next = tmp;
        newhead.next = head;
        return newhead;
    }
    //2.迭代
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode newhead = new ListNode(0);
        newhead.next = head;
        ListNode prev = newhead;
        ListNode cur = prev.next;
        ListNode curN = cur.next;
        ListNode curNN = curN.next;
        while(cur!=null&&curN!=null){
            //交换节点
            prev.next = curN;
            curN.next = cur;
            cur.next = curNN;
            //修改指针
            prev = cur;
            cur = curNN;
            if(cur!=null){
                curN = cur.next;
            }
            if(curN!=null){
                curNN = curN.next;
            }
        }
        return newhead.next;
    }

    public void reorderList(ListNode head) {
        if(head==null||head.next == null||head.next.next==null){
            return;
        }
        //中间结点
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //中间之后逆序
        ListNode newhead = new ListNode(0);
        ListNode cur = slow.next;
        //分离链表
        slow.next = null;
        //逆序
        while(cur!=null){
            ListNode curN = cur.next;
            cur.next = newhead.next;
            newhead.next = cur;
            cur = curN;
        }
        //合并
        ListNode head1 = head;
        ListNode head2 = newhead.next;
        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        while(head1!=null){
            prev.next = head1;
            head1 = head1.next;
            prev = prev.next;
            if(head2!=null){
                prev.next = head2;
                head2 = head2.next;
                prev = prev.next;
            }
        }
    }
}
